#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define MAXSIZE 100
#define MaxSize 100
typedef struct
{	
	char data[10];
	int length;			//串长
}SqString;

typedef struct node
{ 
	SqString Husband;
	SqString Wife;
	struct node *lchild; //指向左孩子节点
	struct node *rchild; //指向右孩子节点
} BTNode;

void StrCopy(SqString &s,SqString t)	//串复制
{
	int i;
	for (i=0;i<t.length;i++)
		s.data[i]=t.data[i];
	s.length=t.length;
}

void StrAssign(SqString &s,char cstr[])	//字符串常量赋给串s
{
	int i;
	for (i=0;cstr[i]!='\0';i++)
		s.data[i]=cstr[i];
	s.length=i;
}

bool StrEqual(SqString s,SqString t)	//判串相等
{
	bool same=true;
	int i;
	if (s.length!=t.length)				//长度不相等时返回0
		same=false;
	else 
		for (i=0;i<s.length;i++)
			if (s.data[i]!=t.data[i])	//有一个对应字符不相同时返回0
			{	same=false;
				break;
			}
	return same;
}

void DispStr(SqString s)	//输出串s
{
	int i;
	if (s.length>0)
	{	for (i=0;i<s.length;i++)
		printf("%c",s.data[i]);
	}
	printf(" ");
}

void CreateBTree(BTNode * &b,char *str)	//创建家谱二叉树
{
	BTNode *St[MAXSIZE],*p=NULL;
	SqString husband;
	SqString wife;

	
	int top=-1,k,j=0;  
	char ch;
	b=NULL;				//建立的二叉树初始时为空
	ch=str[j];
	while(ch!='\0')  	//str未扫描完时循环
	{
		switch(ch) 
		{
			case '(':top++;St[top]=p;k=1; break;		//为左孩子节点
			case ')':top--;break;
			case ',':k=2; break;                      		//为孩子节点右节点
			default:p=(BTNode *)malloc(sizeof(BTNode));
			if(str[j]=='[')
			{
				j++;
				int count = 0;
				while(str[j]!=','&&str[j]!=']')
				{
					husband.data[count] = str[j];
					j++;
					count++;
				}
				husband.data[count] = '\0';
				husband.length = count;
				
				if(str[j]==',')
				{
					j++;
					count = 0;
					while(str[j]!=']')
					{
						wife.data[count] = str[j];
						count++;
						j++;
					}
					
					wife.length = count;
					wife.data[count] = '\0';
				}
				else if(str[j]==']')
				{
					wife.data[0] = '\0';
				}
			}
			else
				printf("输入格式错误\n");
			
			StrCopy(p->Husband,husband);
			StrCopy(p->Wife,wife);
			
			p->lchild=p->rchild=NULL;
			if (b==NULL)                    	 	//*p为二叉树的根节点
				b=p;
			else  								//已建立二叉树根节点
			{	
				switch(k) 
				{
					case 1:St[top]->lchild=p;break;
					case 2:St[top]->rchild=p;break;
				}
			}
		}
		j++;
		ch=str[j];
	}
}


void Display(BTNode *b)
{
	printf("[");
	printf("丈夫：");
	DispStr(b->Husband);
	if(b->Wife.data[0]!='\0')
	{
		printf("妻子：");
		DispStr(b->Wife);
	}
	printf("]");
}

void DispBTree(BTNode *b) 
{
	if (b!=NULL)
	{	
		printf("[");
		printf("丈夫：");
		DispStr(b->Husband);
		if(b->Wife.data[0]!='\0')
		{
			printf("妻子：");
			DispStr(b->Wife);
		}
		printf("]");
		if (b->lchild!=NULL || b->rchild!=NULL)
		{	printf("(");						//有孩子节点时才输出(
			DispBTree(b->lchild);				//递归处理左子树
			if (b->rchild!=NULL) printf(",");	//有右孩子节点时才输出,
			DispBTree(b->rchild);				//递归处理右子树
			printf(")");						//有孩子节点时才输出)
		}
	}
}


void DestroyBTree(BTNode *&b)
{	if (b!=NULL)
{	DestroyBTree(b->lchild);
	DestroyBTree(b->rchild);
	free(b);
}
}


int FindNode(BTNode *b,SqString x,int count) 
{
	//找到某人所在行
	int p;
	if (b==NULL)
		return 0;
	else if (StrEqual(x,b->Husband)||StrEqual(x,b->Wife))
		return count;
	else  
	{
		p=FindNode(b->lchild,x,count+1);
		if (p!=0) 
			return p;
		else 
			return FindNode(b->rchild,x,count+1);
	}
	return 0;
}

typedef struct 
{	BTNode *data[MaxSize];				//存放队中元素
	int front,rear;						//队头和队尾指针
} SqQueue;								//顺序队类型
void InitQueue(SqQueue *&q)				//初始化队列
{	q=(SqQueue *)malloc (sizeof(SqQueue));
	q->front=q->rear=0;
}
void DestroyQueue(SqQueue *&q)			//销毁队列
{
	free(q);
}
bool QueueEmpty(SqQueue *q)				//判断队列是否为空
{
	return(q->front==q->rear);
}
bool enQueue(SqQueue *&q,BTNode *e)		//进队列
{	if ((q->rear+1)%MaxSize==q->front)	//队满上溢出
	return false;
	q->rear=(q->rear+1)%MaxSize;
	q->data[q->rear]=e;
	return true;
}
int Count(SqQueue *&q)					//求队列中的元素个数 
{
	return (q->rear-q->front+MaxSize)%MaxSize;
}
bool deQueue(SqQueue *&q,BTNode *&e)	//出队列
{	if (q->front==q->rear)				//队空下溢出
	return false;
	q->front=(q->front+1)%MaxSize;
	e=q->data[q->front];
	return true;
}

//分层次的层次遍历算法
void LevelOrder1(BTNode *b,int hang)			//分层次的层次遍历算法 
{
	BTNode *p;
	SqQueue *qu;
	InitQueue(qu);					//初始化队列
	int curl=1;						//表示当前层次(初始化为1) 
	enQueue(qu,b);					//根结点指针进入队列
	while (!QueueEmpty(qu))			//队不为空循环
	{
		if(curl==hang) break;
		printf("第%d层: ",curl); 
		int cnt=Count(qu);		//求当前层次的结点个数
		for(int i=0;i<cnt;i++)		//循环cnt次访问当前层的全部结点 
		{ 
			deQueue(qu,p);				//出队结点p
			DispStr(p->Husband);
			if(p->Wife.data[0]!='\0')
				DispStr(p->Wife);
			if (p->lchild!=NULL)		//有左孩子时将其进队
				enQueue(qu,p->lchild);
			if (p->rchild!=NULL)		//有右孩子时将其进队
				enQueue(qu,p->rchild);
		}
		curl++;
		printf("\n"); 
	} 
}
void LevelOrder2(BTNode *b,int hang)			//分层次的层次遍历算法 
{
	BTNode *p;
	SqQueue *qu;
	InitQueue(qu);					//初始化队列
	int curl=1;						//表示当前层次(初始化为1) 
	enQueue(qu,b);					//根结点指针进入队列
	while (!QueueEmpty(qu))			//队不为空循环
	{
		
		int cnt=Count(qu);		//求当前层次的结点个数
		for(int i=0;i<cnt;i++)		//循环cnt次访问当前层的全部结点 
		{ 
			deQueue(qu,p);				//出队结点p
			if(curl==hang)
			{
				DispStr(p->Husband);
			}
			if (p->lchild!=NULL)		//有左孩子时将其进队
				enQueue(qu,p->lchild);
			if (p->rchild!=NULL)		//有右孩子时将其进队
				enQueue(qu,p->rchild);
		}
		curl++;
	} 
}

//(1) 查找某人(参数为父亲姓名或者母亲姓名)的孩子们。
void Search_Childs(BTNode *b,SqString x)
{
	if(b!=NULL)
	{
		if (StrEqual(x,b->Husband)||StrEqual(x,b->Wife))
		{
			//打印孩子
			if(b->lchild!=NULL)
				DispStr(b->lchild->Husband);
			if(b->rchild!=NULL)
				DispStr(b->rchild->Husband);
			//返回
			return;
		}
		Search_Childs(b->lchild,x);
		Search_Childs(b->rchild,x);
		
	}
}

//(2) 查找某人的所有祖先，如苏轼的祖先：祖父母苏序和史氏，伯父母苏涣和杨氏，父母苏洵和程氏。
void Search_Ancestor(BTNode*b,SqString x)
{
	int hang = FindNode(b,x,1);
	LevelOrder1(b,hang);
}

//(3) 查找某人同代的所有兄弟姐妹，如跟苏辙同一代的兄弟姐们包括：堂兄弟苏不欺和苏不疑，兄弟苏轼。
void Search_Sibling(BTNode*b,SqString x)
{
	int hang = FindNode(b,x,1);
	LevelOrder2(b,hang);
}

//(4) 给某人添加孩子。
int ADD_Kid(BTNode* b, SqString name, SqString kid) {
	if (b == NULL) 	return 0;
	
	// 检查当前节点是否为目标父母
	if (StrEqual(b->Husband, name) || StrEqual(b->Wife, name)) {
		// 尝试添加到左孩子
		if (b->lchild == NULL) {
			b->lchild = (BTNode*)malloc(sizeof(BTNode)); // 分配内存
			StrCopy(b->lchild->Husband, kid); 
			b->lchild->Wife.data[0] = '\0';
			
			b->lchild->lchild = NULL; // 初始化子节点
			b->lchild->rchild = NULL;
			return 1;
		}
		// 尝试添加到右孩子
		else if (b->rchild == NULL) {
			b->rchild = (BTNode*)malloc(sizeof(BTNode)); // 分配内存
			StrCopy(b->rchild->Husband, kid); 
			b->rchild->Wife.data[0] = '\0';
			b->rchild->lchild = NULL; // 初始化子节点
			b->rchild->rchild = NULL;
			return 1;
		} 
		else {
			printf("孩子数已满，无法添加\n");
			return 0;
		}
	}
	
	// 递归调用，试图在左孩子和右孩子中添加
	if (ADD_Kid(b->lchild, name, kid)) {
		return 1; // 如果在左边成功添加
	}
	if (ADD_Kid(b->rchild, name, kid)) {
		return 1; // 如果在右边成功添加
	}
	
	return 0; // 没有成功添加
}

//(5) 某单身人士结婚后添加妻子姓名。
int ADD_Wife(BTNode* b, SqString name, SqString Wife) {
	
	if (b == NULL) {
		return 0;
	}
	
	// 检查当前节点是否为目标父母
	if (StrEqual(b->Husband, name)) {
		if (b->Wife.data[0] == '\0') {
			StrCopy(b->Wife, Wife); 
			return 1;
		} else {
			printf("已有妻子，无法添加\n");
			return 0;
		}
	}
	// 递归调用，试图在左孩子和右孩子中查找
	if (ADD_Wife(b->lchild, name, Wife)) 	return 1; // 如果在左边成功添加

	if (ADD_Wife(b->rchild, name, Wife))	return 1; // 如果在右边成功添加

	
	return 0; // 没有成功添加
}


void FirstQuestion(BTNode*b)
{
	char str[20] = {'\0'};
	SqString name;
	printf("(1) 查找某人(参数为父亲姓名或者母亲姓名)的孩子们：");
	scanf("%s",str);
	StrAssign(name,str);
	printf("他的孩子：");
	Search_Childs(b,name);
	printf("\n");
}

void SecondQuestion(BTNode*b)
{
	char str[20] = {'\0'};
	SqString name;
	printf("\n(2) 查找某人的所有祖先,某人：");
	scanf("%s",str);
	StrAssign(name,str);
	int num = FindNode(b,name,1);
	if(num==0) printf("家谱中没有这个人！\n");
	else{
		printf("所在行数：%d\n",num);
		Search_Ancestor(b,name);
	}
	printf("\n");
}

void ThirdQuestion(BTNode*b)
{
	int num = 0;
	char s9t3r[20] = {'\0'};
	SqString name;
	printf("(3) 查找某人同代的所有兄弟姐妹,某人：");
	scanf("%s",s9t3r);
	StrAssign(name,s9t3r);
	num = FindNode(b,name,1);
	if(num==0) printf("家谱中没有这个人！\n");
	else{
		printf("所在行数：%d\n",num);
		Search_Sibling(b,name);
	}
	printf("\n");
	
}

void FourthQuestion(BTNode*b)
{
	int n9u3m = 0;
	char str[20] = {'\0'};
	SqString name;
	printf("\n(4) 给某人添加孩子,某人：");
	scanf("%s",str);
	StrAssign(name,str);
	char child[15] = {'\0'};
	SqString kid;
	printf("孩子姓名：");
	scanf("%s",child);
	StrAssign(kid,child);
	
	n9u3m = ADD_Kid(b,name,kid);
	
	if(n9u3m==0) printf("添加失败！\n");
	else printf("添加成功！\n");
	printf("\n");
	
}

void FifthQuestion(BTNode*b)
{
	char s9t3r[20] = {'\0'};
	SqString name;
	printf("\n(5) 某单身人士结婚后添加妻子姓名,某人：");
	scanf("%s",s9t3r);
	StrAssign(name,s9t3r);
	char wif[15] = {'\0'};
	SqString Wife;
	printf("妻子姓名：");
	scanf("%s",wif);
	StrAssign(Wife,wif);
	int num = ADD_Wife(b,name,Wife);
	if(num==0) printf("添加失败！\n");
	else printf("添加成功！\n");
	printf("\n");

	
}

void menu()
{
	printf("**********************************************\n");
	printf("*******  1.查找某人的孩子们               ****\n");
	printf("*******  2.查找某人的所有祖先             ****\n");
	printf("*******  3.查找某人同代的所有兄弟姐妹    ****\n");
	printf("*******  4.给某人添加孩子                 ****\n");
	printf("*******  5.给某单身人士结婚后添加妻子姓名 ****\n");
	printf("*******  6.输出家谱二叉树                 ****\n");
	printf("*******  7.清屏                           ****\n");
	printf("*******  0.退出                           ****\n");
	
	printf("**********************************************\n");
	
}

void Demo(BTNode*b)
{
	printf("b: "); 
	DispBTree(b);
	printf("\n");
}
int main()
{
	BTNode *b993;
	CreateBTree(b993,(char*)"[苏序,史氏]([苏涣,杨氏]([苏不欺,蒲氏],[苏不疑]),[苏洵,程氏]([苏轼,王弗],[苏辙,史氏]))");

	//23012739
	int i9n3put = 0;
	do{
		menu();
		printf("请输入操作：>");
		scanf("%d",&i9n3put);
		switch(i9n3put)
		{
		case 1:
			FirstQuestion(b993);
			break;
		case 2:
			SecondQuestion(b993);
			break;
		case 3:
			ThirdQuestion(b993);
			break;
		case 4:
			FourthQuestion(b993);
			break;
		case 5:
			FifthQuestion(b993);
			break;
		case 6:
			Demo(b993);
			break;
		case 7:
			system("cls");
			break;
		case 0:
			printf("退出家谱图！\n");
			break;
		default:
			printf("输入错误请重新输入");
		}
	}while(i9n3put);
	
	DestroyBTree(b993);
	return 0;
}
